(*** Extensible arrays ***)

(* enforced invariant. The last element in the array is the default element used at creation time and is not accessible. *)
type 'a t = {
    mutable array : 'a array;
    mutable size : int
}

let ensure_size ea n =  
  let l = Array.length ea.array in
  if l < (n+2) then begin
    let new_l = max 1 (((n+2) / l + 1) * l) in 
    let new_array = Array.make new_l ea.array.(l - 1) in
    Array.blit ea.array 0 new_array 0 l;
    ea.array <- new_array
  end

let create def = { array = [|def|]; size = 0 }

let set ea n v =    
  if n < 0 then failwith "set";
  ensure_size ea n;
  ea.array.(n) <- v;
  ea.size <- max ea.size (n+1)

let delete ea n =
  if (n >= ea.size or n < 0) then failwith "remove";
  Array.blit ea.array (n+1) ea.array n (Array.length ea.array - n - 1);
  ea.size <- ea.size - 1
	
let insert ea n = 
	if n > ea.size then failwith "insert";
	ensure_size ea (ea.size+1);
	Array.blit ea.array n ea.array (n+1) (Array.length ea.array - n - 2);
	ea.array.(n) <- ea.array.(Array.length ea.array -1);
	ea.size <- ea.size + 1

let get ea n = ea.array.(n)

let get_size ea = ea.size

let iterate ea f = for i = 0 to ea.size - 1 do f i ea.array.(i) done
